Để thực hiện lý tưởng của mình, Nguyễn An Ninh nhận định cần phải xây dựng một tổ chức nhằm mục đích giáo dục ý thức chính trị cho quần chúng. Do việc chính quyền thực dân Nam Kỳ cấm ông diễn thuyết trước công chúng, từ cuối năm 1924 đầu năm 1925, ông bắt đầu đi gây dựng cơ sở dưới hình thức bán báo, bán dầu cù là, tại vùng Hóc Môn - Bà Điểm, nơi gia đình ông đang sinh sống, sau đó mở rộng sang vùng Củ Chi, Đức Hòa. Trong những ngày đầu vận động, ông được sự giúp sức của 2 người cháu vợ là Trương Văn Khải và Trương Văn Bang.

Sau khi chí sĩ Phan Chu Trinh về nước, ông cùng với ông Mai Văn Ngọc bàn bạc về cách thức tổ chức Đảng Thanh niên Cao vọng. Được sự giúp đỡ của ông Phan Văn Hùm, ông Ninh đi khắp Nam Kỳ để gây dựng cơ sở. Nông dân các tỉnh nghe tin ông Ninh đi đến đâu là xúm lại để xem mặt và nghe ông nói chuyện. Ông thường hẹn mọi người đến buổi tối thì đến chùa hoặc ra cánh đồng trống để diễn thuyết, mỗi buổi diễn thuyết như thế chỉ có tối đa 19 người để tránh bị chính quyền làm khó dễ. Qua những chuyến đi này, hai ông chọn ra những thanh niên ưu tú, có trình độ, giàu lòng yêu nước sau đó giới thiệu về cho ông Mai Văn Ngọc tiếp tục huấn luyện để kết nạp. Mỗi chuyến đi thường kéo dài khoảng 1 tuần hoặc 10 ngày, địa điểm đi được lựa chọn trước. Ban ngày hai ông đi khắp hang cùng ngõ hẻm ở nông thôn, đói đã có lương khô mang theo, khát nước thì vào nhà dân xin nước uống, ban đêm hai ông thường xin vào ngủ ở chùa hoặc khi lỡ độ đường thì ngủ luôn trên sạp hàng ở chợ. Họ không ngủ ở nhà dân vì sợ liên lụy đến bà con.